package com.iweb;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>(); // 存放路径
        Deque<TreeNode> deque = new LinkedList<>(); // 存放遍历的结果, 当回溯的时候移除队列最后的值
        if (root == null) return result;

        // 递归
        backtrack(result, deque, root);
        return result;
    }

    // 递归
    public void backtrack(List<String> result, Deque<TreeNode> deque, TreeNode root) {
        deque.add(root);
        // 判断回溯 找到叶子节点
        if (root.left == null && root.right == null) { // 判断叶子节点
            // 拼接 deque 中的结果 = 路径
            String str = "";
            for (TreeNode node : deque) {
                str += node.val;
                str += "->";
            }
            // 移除最后的 ->
            str = str.substring(0, str.length() - 2);
            result.add(str); // 路径保存到 result 中
        }

        // 先序
        if (root.left != null) {
            backtrack(result, deque, root.left);
            deque.removeLast(); // 回溯
        }

        if (root.right != null) {
            backtrack(result, deque, root.right);
            deque.removeLast(); // 回溯

        }

    }

    public static void main(String[] args) {

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(6);

        Solution solution = new Solution();
        List<String> list = solution.binaryTreePaths(root);
        System.out.println(list);
    }
}


